public class Solution69 {
    public int mySqrt(int x) {
        if (x == 0 || x == 1) {
            return x;
        }
        int l = 1, r = x, m = x / 2;
        while (l <= r) {
            if (x / m < m) {
                r = m - 1;
            } else if (x / m > m) {
                l = m + 1;
            } else {
                return m;
            }
            if (x / l < l) {
                return l - 1;
            }
            if (x / r > r) {
                return r;
            }
            m = (l + r) / 2;
        }
        return l - 1;
    }
}
